package 蓝桥杯算法;

import java.util.Arrays;

public class day20 {
    public static void main(String[] args) {
        day20 a = new day20();
        System.out.println(a.intersal(4));
        System.out.println(a.climb(3));
        int[] cost = {1, 100, 1, 1, 1, 100, 1, 1, 100, 1};
        System.out.println(a.minclimb(cost));
        System.out.println(a.finways(3, 7));
        int[][] arr = {{0, 0, 0}, {0, 1, 0}, {0, 0, 0}};
        System.out.println(a.finways2(arr));
    }

    public int intersal(int n) {
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        } else {
            return intersal(n - 1) + intersal(n - 2);
        }
    }

    public int fib(int n) {
        if (n < 2) {
            return n;
        }
        int a = 0, b = 1, c = 0;
        for (int i = 1; i < n; i++) {
            c = a + b;
            a = b;
            b = c;//下一个值已经得到
        }
        return c;
    }

    public int climb(int n) {
        if (n == 0) {
            return 1;
        }
        if (n == 1) {
            return 1;
        } else {
            return climb(n - 1) + climb(n - 2);
        }
    }

    public int minclimb(int[] cost) {
        int len = cost.length;
        int[] dp = new int[len + 1];
        dp[0] = 0;
        dp[1] = 0;
        for (int i = 2; i <= len; i++) {
            dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        }
        return dp[len];
    }

    /* public int eerseover(int[][] interals){
         //数组的比较
         Arrays.sort(interals,(a,b)->{
             return Integer.compare(a[0],b[0]);
         });

     }*/
    public int finways(int m, int n) {//找不同路径
        int count = 0;
        int[][] path = new int[m][n];
        for (int i = 0; i < m; i++) {
            path[i][0] = 1;
        }
        for (int i = 0; i < n; i++) {
            path[0][i] = 1;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                path[i][j] = path[i - 1][j] + path[i][j - 1];
            }
        }
        return path[m - 1][n - 1];
    }

    public int finways2(int[][] obstackleGrid) {
        int len = obstackleGrid.length;
        int[][] ways = new int[len][len];
        if (obstackleGrid[0][0] == 1 || obstackleGrid[len - 1][len - 1] == 1) {
            return 0;//开始和结束位置被阻塞
        }
            for (int i = 0; i < len; i++) {
                if (obstackleGrid[i][0] != 1) {
                    ways[i][0] = 1;
                }
            }
            for (int j = 0; j < len; j++) {
                if (obstackleGrid[0][j] != 1) {
                    ways[0][j] = 1;
                }
            }
            for (int i = 1; i < len; i++) {
                for (int j = 1; j < len; j++) {
                    if (obstackleGrid[i][j] != 1) {
                        ways[i][j] = ways[i - 1][j] + ways[i][j - 1];
                    } else {
                        ways[i][j] = 0;
                    }

                }
            }
            return ways[len-1][len-1];
        }


    }


